package edu.whu.rose.clock.kps.algorithm.banks2;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;

import edu.whu.rose.clock.kps.algorithm.banks1.AnswerTree;
import edu.whu.rose.clock.kps.algorithm.banks1.BackwardExpandingSearch;
import edu.whu.rose.clock.kps.algorithm.banks1.SPVertex;
import edu.whu.rose.clock.kps.graph.GraphMatrix;
import edu.whu.rose.clock.ssql.util.ExpandableIntArray;
import edu.whu.rose.clock.ssql.util.SequentialIntArray;
import edu.whu.rose.clock.util.priorityqueue.MaxFibonacciHeapPQ;
import edu.whu.rose.clock.util.priorityqueue.UnderflowException;

public class BidirectionalExpandingSearch {

	private GraphMatrix graph;
	private int[][] sets;
	private int k;
	
	private MaxFibonacciHeapPQ<ActivationVertex> inHeap;
	private MaxFibonacciHeapPQ<ActivationVertex> outHeap;
	
	private HashMap<Integer, ActivationVertex> vertexes;
	
	private int dmax = 8;
	
	private ActivationVertex[] union;
	private AnswerTree[] topK;
	private int size;
	
	public BidirectionalExpandingSearch(GraphMatrix graph, int[][] sets, int k) {
		this.graph = graph;
		this.sets = sets;
		this.k = k;
	}
	
	public static void main(String[] args) {
		GraphMatrix spg = new GraphMatrix(11012);
		spg.loadEdges("graph/edge.txt");
		
		int[][] sets = new int[][]{{300}, {400, 500}};
		
		BidirectionalExpandingSearch bes = new BidirectionalExpandingSearch(spg, sets, 10);
		bes.init();
		bes.search();
		
		for (int i = 0; i < bes.getSize(); i++) {
			AnswerTree at = bes.getAnswer(i);
			System.out.print("Rank " + (i + 1) + ": root[" + at.getRoot() + "] ");
			
			for (int j = 0; j < at.getLeafNumber(); j++) {
				int[] path = at.getPath(j);
				System.out.print("( ");
				if (path != null) {
					for (int m = 0; m < path.length; m++) {
						System.out.print(path[m] + ", ");
					}
				}
				System.out.print(" )");
			}
			System.out.println();
		}
	}
	
	public void init() {
		union = unionSets();
		inHeap= new MaxFibonacciHeapPQ<ActivationVertex>();
		outHeap= new MaxFibonacciHeapPQ<ActivationVertex>();
		vertexes = new HashMap<Integer, ActivationVertex>();
		for (int i = 0; i < union.length; i++) {
			int indexID = inHeap.enqueue(union[i]);
			union[i].setIndexID(indexID);
			union[i].setIn(true);
			vertexes.put(new Integer(union[i].getID()), union[i]);
		}
		topK = new AnswerTree[k];
		size = 0;
	}
	
	private ActivationVertex[] unionSets() {
		HashMap<Integer, ActivationVertex> avset = new HashMap<Integer, ActivationVertex>();
		for (int i = 0; i < sets.length; i++) {
			int[] set = sets[i];
			for (int j = 0; j < set.length; j++) {
				ActivationVertex av = avset.get(new Integer(set[j]));
				if (av == null) {
					av = new ActivationVertex(set[j], sets.length);
					av.setActivation(i, 1d / (double) sets[i].length);
					av.setDistances(i, 0d);
					avset.put(new Integer(set[j]), av);
				}
				else {
					av.setActivation(i, 1d / (double) sets[i].length);
				}
			}
		}
		return avset.values().toArray(new ActivationVertex[avset.size()]);
	}
	
	public void search() {
		while (!inHeap.isEmpty() || !outHeap.isEmpty()) {
			try {
				if (outHeap.isEmpty() || 
						(!inHeap.isEmpty() && 
								inHeap.findMax().getTotalActivation() > outHeap.findMax().getTotalActivation())) {
					ActivationVertex maxav = inHeap.dequeueMax();
					maxav.setIn(false);
					maxav.setInX(true);
					
					if (isComplete(maxav)) {
						
					}
					
					if (maxav.getDepth() < dmax) {
						int [] neighbors = graph.genNeighbors(maxav.getID());
						double weight = Math.log1p(neighbors.length)/Math.log(2d);
						for (int i = 0; i < neighbors.length; i++) {
							int neighbor = neighbors[i];
							ActivationVertex av = vertexes.get(new Integer(neighbor));
							if (av == null) {
								av = new ActivationVertex(neighbor, sets.length);
								vertexes.put(new Integer(neighbor), av);
							}
							exploreEdge(av, maxav, weight);
							if (!av.isInX()) {
								av.setDepth(maxav.getDepth() + 1);
								int indexID = inHeap.enqueue(av);
								av.setIndexID(indexID);
								av.setIn(true);
							}
						}
						if (!maxav.isOutX()) {
							int indexID = outHeap.enqueue(maxav);
							maxav.setIndexID(indexID);
							maxav.setOut(true);
						}
					}
				}
				else {
					ActivationVertex maxav = outHeap.dequeueMax();
					maxav.setOut(false);
					maxav.setOutX(true);
					
					if (isComplete(maxav)) {
						
					}

					if (maxav.getDepth() < dmax) {
						int [] neighbors = graph.genNeighbors(maxav.getID());
						for (int i = 0; i < neighbors.length; i++) {
							int neighbor = neighbors[i];
							ActivationVertex av = vertexes.get(new Integer(neighbor));
							if (av == null) {
								av = new ActivationVertex(neighbor, sets.length);
								vertexes.put(new Integer(neighbor), av);
							}
							exploreEdge(av, maxav, 1d);
							if (!av.isOutX()) {
								av.setDepth(maxav.getDepth() + 1);
								int indexID = outHeap.enqueue(av);
								av.setIndexID(indexID);
								av.setOut(true);
							}
						}
					}
				}
				
				
				
			}
			catch (UnderflowException ex) {
				ex.printStackTrace();
			}
			
		}
	}
	
	private boolean isComplete(ActivationVertex av) {
		for (int i = 0; i < sets.length; i++) {
			if (av.getDistances(i) == Double.MAX_VALUE) {
				return false;
			}
		}
		return true;
	}

	private HashSet<HashSet<Integer>> crossProduct(int origin, int i, ExpandableIntArray[] nodeLists) {
		HashSet<HashSet<Integer>> results = new HashSet<HashSet<Integer>>();
		HashSet<Integer> seed = new HashSet<Integer>();
		seed.add(new Integer(origin));
		results.add(seed);
		for (int j = 0; j < nodeLists.length; j++) {
			if (j != i) {
				if (nodeLists[j].getSize() == 0) {
					return null;
				}
				ArrayList<HashSet<Integer>> tuples = new ArrayList<HashSet<Integer>>();
				Iterator<HashSet<Integer>> it = results.iterator();
				while (it.hasNext()) {
					HashSet<Integer> tuple = it.next();
					it.remove();
					for (int k = 0; k < nodeLists[j].getSize(); k++) {
						int node = nodeLists[j].get(k);
						if (node == 0) {
							continue;
						}
						Integer n = new Integer(node);
						if (!tuple.contains(n)) {
							HashSet<Integer> newTuple = new HashSet<Integer>();
							newTuple.addAll(tuple);
							newTuple.add(n);
							tuples.add(newTuple);
						}
						else {
							tuples.add(tuple);
						}
					}
				}
				results.addAll(tuples);
			}
		}
		return results;
	}
	
	private void exploreEdge(ActivationVertex av, ActivationVertex maxav, double weight) throws UnderflowException {
		int[] neighbors = graph.genNeighbors(av.getID());
		double w = Math.log1p(neighbors.length)/Math.log(2d);
		for (int i = 0; i < sets.length; i++) {
			if (av.getDistances(i) > maxav.getDistances(i) + 1) {
				av.setPredecessors(i, maxav.getID());
				av.setDistances(i, maxav.getDistances(i) + 1);
				attach(av, i, neighbors);
				if (isComplete(av)) {
					
				}
			}
			double newAct = maxav.getActivation(i) / weight;
			if (av.getActivation(i) < newAct) {
				av.setActivation(i, newAct);
				activate(av, i, neighbors, w);
			}
		}
	}
	
	private void attach(ActivationVertex av, int group, int[] neighbors) {
		if (av.isIn()) {
			
		}
		
		for (int i = 0; i < neighbors.length; i++) {
			int neighbor = neighbors[i];
			ActivationVertex av2 = vertexes.get(new Integer(neighbor));
			if (av2 != null) {
				if (av2.getDistances(group) > av.getDistances(group) + 1) {
					av2.setPredecessors(i, av.getID());
					av2.setDistances(i, av.getDistances(i) + 1);
					int[] temp = graph.genNeighbors(av2.getID());
					attach(av2, group, temp);
				}
			}
		}
	}
	
	private void activate(ActivationVertex av, int group, int[] neighbors, double weight) throws UnderflowException {
		if (av.isIn()) {
			inHeap.increaseKey(av.getIndexID(), av);
		}
		for (int i = 0; i < neighbors.length; i++) {
			int neighbor = neighbors[i];
			ActivationVertex av2 = vertexes.get(new Integer(neighbor));
			if (av2 != null) {
				double newAct = av.getActivation(group) / weight;
				if (av2.getActivation(group) < newAct) {
					av2.setActivation(group, newAct);
					int[] n = graph.genNeighbors(av2.getID());
					double w = Math.log1p(n.length)/Math.log(2d);
					activate(av2, i, n, w);
				}
			}
		}
	}
	
	private AnswerTree genAnswerTree(int root, HashSet<Integer> tuple, 
			int origin, HashMap<Integer, int[]> allPredecessors) {
		Iterator<Integer> it = tuple.iterator();
		int[] leaves = new int[tuple.size()];
		int[][] paths = new int[tuple.size()][];
		SequentialIntArray allVertexes = new SequentialIntArray();
		allVertexes.insert(root);
		int i = 0;
		
		while (it.hasNext()) {
			leaves[i] = it.next().intValue();
			paths[i] = getPath(root, leaves[i], allVertexes, 
					allPredecessors.get(new Integer(leaves[i])));
			i++;
		}
		
		return new AnswerTree(root, leaves, paths, allVertexes.getArray());
	}
	
	private int[] getPath(int root, int origin, 
			SequentialIntArray allVertexes, int[] predecessors) {
		ExpandableIntArray eia = new ExpandableIntArray();
		int current = root;
		
		while (current != origin) {
			current = predecessors[current - 1];
			if (current == 0) {
				return null;
			}
			allVertexes.insert(current);
			eia.add(current);
		}
		
		return eia.toArray();
	}
	
	private void addTopKAnswer(AnswerTree at) {
		for (int i = 0; i < size; i++) {
			int x = at.compare(topK[i]);
			if (x < 0) {
				return;
			}
			else if (x > 0) {
				System.out.println();
			}
		}
		topK[size] = at;
		size++;
	}

	public int getK() {
		return k;
	}
	
	public int getSize() {
		return size;
	}
	
	public AnswerTree[] getAnswers() {
		return topK;
	}

	public AnswerTree getAnswer(int index) {
		return topK[index];
	}
}
